package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2021/7/13.<br><br>
 *
 * 丑数Ⅱ
 */
public class Topic264 {

    public static void main(String[] args) {
        Topic264 instance = new Topic264();

        System.out.println(instance.nthUglyNumber(10));
        System.out.println(instance.nthUglyNumber(8));
        System.out.println(instance.nthUglyNumber(14));
        System.out.println(instance.nthUglyNumber(1));
    }

    public int nthUglyNumber(int n) {
        int[] array = new int[n];
        array[0] = 1;
        int index1 = 0;
        int index2 = 0;
        int index3 = 0;

        for(int i = 1; i < n; i++) {
            int next = Math.min(Math.min(array[index1] * 2, array[index2] * 3), array[index3] * 5);

            if(next == array[index1] * 2) {
                index1++;
            }

            if(next == array[index2] * 3) {
                index2++;
            }

            if(next == array[index3] * 5) {
                index3++;
            }

            array[i] = next;
        }

        return array[n - 1];
    }
}
